﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

/*
* 题目：环形链表Ⅰ
* 内容：给你一个链表的头节点 head ，判断链表中是否有环。
* 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
* 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
* 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
* 如果链表中存在环，则返回 true 。 否则，返回 false 
* 链接：https://leetcode-cn.com/problems/linked-list-cycle
* 
*/

/*
* 思路：利用快慢指针来解决该问题
* 快指针：一次运动两个节点
* 慢指针：一次运动一个节点
* 当快指针为NULL或fast->next为NULL时，表示没有环
* 当快指针fast == slow时表示有环，切当前地址为相遇点的地址
*/

struct ListNode 
{
    int val;
    struct ListNode *next;
};
bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}

/*
* 题目：环形链表Ⅱ
* 内容：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
* 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
* 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
* 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
* 不允许修改 链表。
* 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
*/

/*
* 思路1：利用快慢指针来解决该问题
* 快指针：一次运动两个节点
* 慢指针：一次运动一个节点
* 当快指针为NULL或fast->next为NULL时，表示没有环
* 当快指针fast == slow时表示有环，切当前地址为相遇点的地址
* 根据课堂内容的推理：
* 一个指针从头指针开始运动，另一个在相遇点开始运动，他们将会在入环点相遇
*/

struct ListNode* detectCycle(struct ListNode* head) {
    // 判断是否有环
    struct ListNode* fast, * slow;
    fast = head;
    slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            // 相遇
            struct ListNode* meet = fast;
            // 一个在head，一个在相遇点，两者开始移动，在入环点相遇
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    // 没有环
    return NULL;
}

/*
* 思路2：利用快慢指针来解决该问题
* 快指针：一次运动两个节点
* 慢指针：一次运动一个节点
* 当快指针为NULL或fast->next为NULL时，表示没有环
* 当快指针fast == slow时表示有环，且当前地址为相遇点的地址
* 重新设置两个指针cur_one = head;cur_two = fast -> next;
* 此时问题表示为链表相交的问题，求相交点
* 首先求出两个链表是否相交（环中必然相交），切求出两个链表的长度（迭代）
* 让长的链表先走链表长度差的个位置，在继续一起走，相等时为相交点（入环点）
*/

struct ListNode* detectCycle(struct ListNode* head) {
    // 判断是否有环
    struct ListNode* fast, * slow;
    struct ListNode* head_one, * tur_one, * head_two, * tur_two;
    fast = head;
    slow = head;
    head_one = tur_one = head;
    head_two = tur_two = NULL;
    int num_one = 0;
    int num_two = 0;
    int num = 0;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        // 有环
        if (fast == slow)
        {
            // 相遇
            struct ListNode* meet = fast;
            head_two = tur_two = meet->next;
            // 判断新链表的长度
            while (tur_one != meet)
            {
                num_one++;
                tur_one = tur_one->next;
            }
            while (tur_two != meet)
            {
                num_two++;
                tur_two = tur_two->next;
            }
            // 使长链表先走num个节点
            if (num_one > num_two)
            {
                num = num_one - num_two;
                while (num--)
                {
                    head_one = head_one->next;
                }
            }
            else
            {
                num = num_two - num_one;
                while (num--)
                {
                    head_two = head_two->next;
                }
            }
            // 寻找相交点(入环点)
            while (head_one != head_two)
            {
                head_one = head_one->next;
                head_two = head_two->next;
            }
            return head_one;
        }
    }
    // 没有环
    return NULL;
}